#include <iostream>
#include <vector>
#include <functional> 


bool lessThan(int a, int b) {
    return a < b;
}

bool greaterThan(int a, int b) {
    return a > b;
}

template<typename T>
void heapify(std::vector<T>& vec, int n, int i, bool (*cmp)(T, T)) {
    int largest = i; 
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < n && cmp(vec[left], vec[largest]))
        largest = left;
    if (right < n && cmp(vec[right], vec[largest]))
        largest = right;
    if (largest != i) {
        std::swap(vec[i], vec[largest]);
        heapify(vec, n, largest, cmp);
    }
}


template<typename T>
void heapSort(std::vector<T>& vec, bool (*cmp)(T, T)) {
    int n = vec.size();

    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(vec, n, i, cmp);

    for (int i = n - 1; i >= 0; i--) {
        std::swap(vec[0], vec[i]);
        heapify(vec, i, 0, cmp);
    }
}

template<typename T>
bool checkSorted(const std::vector<T>& vec, bool (*cmp)(T, T)) {
    for (size_t i = 1; i < vec.size(); ++i) {
        if (cmp(vec[i - 1], vec[i])) {
            return false;
        }
    }
    return true;
}